#include <bits/stdc++.h>

using namespace std;

// 让字符串成为回文串的最少插入次数
// 给你一个字符串 s
// 每一次操作你都可以在字符串的任意位置插入任意字符
// 请你返回让s成为回文串的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

class Solution 
{
public:
    // 暴力尝试
    int minInsertions1(string s) 
    {
        int n = s.size();
        return f1(s, 0, n - 1);
    }

	// s[l....r]这个范围上的字符串，整体都变成回文串
	// 返回至少插入几个字符
    int f1(string& s, int left, int right)
    {
        // l <= r
        if(left == right) return 0;
        else if(left + 1 == right) return s[left] == s[right] ? 0 : 1;
        else
        {
            // l...r不只两个字符
            if(s[left] == s[right]) return f1(s, left + 1, right - 1);
            else return 1 + min(f1(s, left + 1, right), f1(s, left, right - 1));
        }
    }

    int minInsertions2(string s) 
    {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        return f2(s, 0, n - 1, dp);
    }

    int f2(string& s, int left, int right, vector<vector<int>>& dp)
    {
        if(dp[left][right] != -1) return dp[left][right];

        int ans = 0;
        if(left == right) ans = 0;
        else if(left + 1 == right) ans = s[left] == s[right] ? 0 : 1;
        else
        {
            if(s[left] == s[right]) ans = f2(s, left + 1, right - 1, dp);
            else ans = 1 + min(f2(s, left + 1, right, dp), f2(s, left, right - 1, dp));
        }
        dp[left][right] = ans;
        return ans; 
    }

    // 严格位置依赖的动态规划
    int minInsertions3(string s) 
    {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for(int l = 0; l < n - 1; ++l)
        {
            dp[l][l + 1] = s[l] == s[l + 1] ? 0 : 1;
        }

        for(int l = n - 3; l >= 0; --l)
        {
            for(int r = l + 2; r < n; ++r)
            {
                if(s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1];
                else dp[l][r] = 1 + min(dp[l][r - 1], dp[l + 1][r]);
            }
        }
        return dp[0][n - 1];
    }

	// 空间压缩
	// 本题有关空间压缩的实现，可以参考讲解067，题目4，最长回文子序列问题的讲解
	// 这两个题空间压缩写法高度相似
	// 因为之前的课多次讲过空间压缩的内容，所以这里不再赘述
    int minInsertions4(string s) 
    {
        int n = s.size();
        if(n < 2) return 0;
        vector<int> dp(n);
        dp[n - 1] = s[n - 2] == s[n - 1] ? 0 : 1;

        for(int l = n - 3, leftDown, backUp; l >= 0; --l)
        {
            leftDown = dp[l + 1];
            dp[l + 1] = s[l] == s[l + 1] ? 0 : 1;
            for(int r = l + 2; r < n; ++r)
            {
                backUp = dp[r];
                if(s[l] == s[r]) dp[r] = leftDown;
                else dp[r] = 1 + min(dp[r - 1], dp[r]);
                leftDown = backUp;
            }
        }
        return dp[n - 1];
    }
};


class Solution 
{
public:
    int minInsertions(string s) 
    {
        int n = s.size();
        int dp[n][n];
        memset(dp, 0, sizeof dp);
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
        return dp[0][n - 1];
    }
};